package com.mdnote.jianzhi_offer.dp;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Offer19 {

    public static void main(String[] args) {
        Offer19 offer19 = new Offer19();
        System.out.println(offer19.isMatch("a", ".*"));
        System.out.println(offer19.isMatch("accd", "accd"));
        System.out.println(offer19.isMatch("accd", "ac.d"));
        System.out.println(offer19.isMatch("accd", "ac*d"));
        System.out.println(offer19.isMatch("", ".*"));
        System.out.println(offer19.isMatch("", ".*c"));
        System.out.println(offer19.isMatch("ab", ".*c"));
        System.out.println(offer19.isMatch("a", ""));
    }

    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }

        HashMap<String, Boolean> memo = new HashMap<>();
        return dp(s, 0, p, 0, memo);
    }
    private boolean _match(String source, int sIndex, String partter, int pIndex, Map<String, Boolean> memo) {

        // Terminator
        if (sIndex == source.length() && pIndex == partter.length()) {
            // 匹配成功
            return true;
        }
        if (sIndex != source.length() && pIndex == partter.length()) {
            // 字符串还有。模式串已经没了，一定失败
            return false;
        }
        // 字符串匹配完，但是模式穿还没匹配完不一定是失败的，可能后面还有*
        // 记忆话
        String key = sIndex + "," + pIndex;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        boolean value = false;
        if (pIndex + 1 < partter.length() && partter.charAt(pIndex + 1) == '*') {
            // 后面是*
            if (sIndex < source.length() && (partter.charAt(pIndex) == '.' || partter.charAt(pIndex) == source.charAt(sIndex))) {
                value = _match(source, sIndex + 1, partter, pIndex + 2, memo) || // 出现1次
                        _match(source, sIndex + 1, partter, pIndex, memo) ||  // 出现多次
                        _match(source, sIndex, partter, pIndex + 2, memo); // 出现0次，如a*a match ab
                memo.put(key, value);
                return value;
            } else {
                // 直接跳过
                value =  _match(source, sIndex, partter, pIndex + 2, memo);
                memo.put(key, value);
                return value;
            }
        }

        // 正常的匹配
        if (sIndex < source.length() && source.charAt(sIndex) == partter.charAt(pIndex) || partter.charAt(pIndex) == '.') {
            value = _match(source, sIndex + 1, partter, pIndex + 1, memo);
            memo.put(key, value);
            return value;
        }

        memo.put(key, value);
        return value;
    }


    /**
     * 匹配
     * @param source 源字符串
     * @param sIndex 源字符串索引
     * @param partter 模式穿
     * @param pIndex 模式串索引
     * @return 匹配结果
     */
    private boolean _match(String source, int sIndex, String partter, int pIndex) {

        // Terminator
        if (sIndex == source.length() && pIndex == partter.length()) {
            // 匹配成功
            return true;
        }
        if (sIndex != source.length() && pIndex == partter.length()) {
            // 字符串还有。模式串已经没了，一定失败
            return false;
        }
        // 字符串匹配完，但是模式穿还没匹配完不一定是失败的，可能后面还有*

        if (pIndex + 1 < partter.length() && partter.charAt(pIndex + 1) == '*') {
            // 后面是*
            if (sIndex < source.length() && (partter.charAt(pIndex) == '.' || partter.charAt(pIndex) == source.charAt(sIndex))) {
                return _match(source, sIndex + 1, partter, pIndex + 2) || // 出现1次
                        _match(source, sIndex + 1, partter, pIndex) ||  // 出现多次
                        _match(source, sIndex, partter, pIndex + 2); // 出现0次，如a*a match ab
            } else {
                // 直接跳过
                return _match(source, sIndex, partter, pIndex + 2);
            }

        }

        // 正常的匹配
        if (sIndex < source.length() && source.charAt(sIndex) == partter.charAt(pIndex) || partter.charAt(pIndex) == '.') {
            return _match(source, sIndex + 1, partter, pIndex + 1);
        }

        return false;
    }

    private static boolean dp(String source, int sIndex, String partern, int pIndex, Map<String, Boolean> memo) {

        // base case
        if (sIndex == source.length() && pIndex == partern.length()) {
            return true;
        }
        if (sIndex != source.length() && pIndex == partern.length()) {
            return false;
        }
        if (sIndex == source.length() && pIndex != partern.length()) {
            // 判断后面的是不是a*b*这种
            if ((partern.length() - pIndex) % 2 != 0) {
                return false;
            }
            for (int p = pIndex; p  < partern.length(); p += 2) {
                if (p + 1 < partern.length() && partern.charAt(p + 1) != '*') {
                    return false;
                }
            }
            return true;
        }

        // memo
        String key = sIndex + "," + pIndex;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // Logic
        boolean value = false;
        if (source.charAt(sIndex) == partern.charAt(pIndex) || partern.charAt(pIndex) == '.') {
            // 匹配
            if (pIndex + 1 < partern.length() && partern.charAt(pIndex + 1) == '*') {
                // 有*
                value = dp(source, sIndex, partern, pIndex + 2, memo) || // 出现0粗
                        dp(source, sIndex + 1, partern, pIndex + 2, memo) || // 出现1次u
                        dp(source, sIndex + 1, partern , pIndex, memo); // 出现多次
            } else {
                // 无*
                value = dp(source, sIndex + 1, partern, pIndex + 1, memo);
            }
        } else {
            // 不匹配
            if (pIndex + 1 < partern.length() && partern.charAt(pIndex + 1) == '*') {
                // 有*
                value = dp(source, sIndex, partern, pIndex + 2, memo);
            } else {
                // 无*
                value = false;
            }
        }

        memo.put(key, value);
        return value;
    }

}
